N - Slimes
区間DPをします。イメージとしては、{10, 20, 30, 40}というのがあった時に、上から順に
{10} → 0
{20} → 0
{30} → 0
{40} → 0
{10, 20} →0+0+30 = 30
{20, 30} →0+0+50 = 50
{30, 40} →0+0+70 = 70
{10, 20, 30} →30+0+60 = 90
{20, 30, 40} → 50+0+90 = 140
{10, 20, 30, 40} → 90+0+100 = 190 … これが答え
という風に区間をだんだん広くしていく感じです。
その時点での答えは、その前の既に計算している小さい部分から錬成できます。（DPに適している！）
DP添字
dp[i][j] 区間i~jまでのスライムを1つにまとめるために必要なコストの最小値 とします。
そうしておいたら最終的にdp[0][n]で答えが取り出せるので…！
初期化
最小値を更新していくので、まず全てをINFLで初期化しておきます
このINFLがミソで、INFだとINFを超えるものが現れる可能性があるのでINFLに
そのあと、dp[i][i](何もない) と dp[i][i+1] (1つだけ) を全て0にしておきます
1つのやつは既にひとつにまとまっているので、コストはゼロになります
遷移
既に計算されているdpの値で、次のdpの値が錬成できないか考える
コツとして、初めの数ターンとか最後の1ターン辺りを考えると思いつきやすい
最初の数ターンを考えてみる
https://gyazo.com/f1b812d84e7c88fe29709452a241d02a
https://gyazo.com/9f3f4d5ae74fb0ed902bec0a189fd7dc
最後のターンを考えてみる
https://gyazo.com/9fc782b5ce7bf4dcafa935ea77cd5dfe
考察をすっごい進めると、「左部分 + 右部分 + できたやつ」 で求められることが分かります。
「できたやつ」のサイズは必ず、その区間の総和になります。なので、「左部分のコスト + 右部分のコスト + その区間の総和」という風にすればいいです。
code:sample.cpp
// iからjまでが左部分、jからi+wが右部分、iからi+wが全体というイメージ
for (int w = 2; w <= n; w++) // w…横幅
for (int i = 0; i + w <= n; i++) // i…左端
for (int j = i + 1; j < i + w; j++) // j…左部分と右部分を分ける境目
実装のコツ
区間DPは半開区間 $ [i, i+w) で持つと振り回しやすいです。